package com.sheng.leetcode.year2023.swordfingerofferspecial.day01;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/02
 * <p>
 * 剑指 Offer II 002. 二进制加法<p>
 * <p>
 * 给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。<p>
 * 输入为 非空 字符串且只包含数字 1 和 0。<p>
 * <p>
 * 示例 1:<p>
 * 输入: a = "11", b = "10"<p>
 * 输出: "101"<p>
 * <p>
 * 示例 2:<p>
 * 输入: a = "1010", b = "1011"<p>
 * 输出: "10101"<p>
 * <p>
 * 提示：<p>
 * 每个字符串仅由字符 '0' 或 '1' 组成。<p>
 * 1 <= a.length, b.length <= 10^4<p>
 * 字符串如果不是 "0" ，就都不含前导零。<p>
 * <p>
 * 注意：本题与主站 67 题相同：<a href="https://leetcode-cn.com/problems/add-binary/">主站 67</a><p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/JFETK5">剑指 Offer II 002. 二进制加法</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword002 {

    @Test
    public void test01() {
        String a = "11", b = "10";
//        String a = "1010", b = "1011";
        System.out.println(new Solution002().addBinary(a, b));
    }
}

class Solution002 {
    public String addBinary(String a, String b) {
        // i 和 j 分别代表字符串 a，b 的最后一个字符的位置
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder builder = new StringBuilder();
        // 循环相加两个字符串相同长度的低位数部分
        while (i >= 0 && j >= 0) {
            int sum = carry;
            sum += a.charAt(i--) - '0';
            sum += b.charAt(j--) - '0';
            carry = sum / 2;
            // 将余数之和拼接起来，拼接到最后再进行反转，即为答案字符串
            builder.append(sum % 2);
        }
        // 如果 a 还没遍历完成（ a 串比 b 串长），则继续遍历添加 a 的剩余部分
        while (i >= 0) {
            int sum = carry + a.charAt(i--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        // 如果 b 还没遍历完成（ b 串比 a 串长），则继续遍历添加 b 的剩余部分
        while (j >= 0) {
            int sum = carry + b.charAt(j--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        // 如果 carry 不等于 0 还有个进位数没加进去，需要补充
        if (carry == 1) {
            builder.append(carry);
        }
        // 反转字符串获得正常结果
        return builder.reverse().toString();
    }
//    public String addBinary(String a, String b) {
//        return Integer.toBinaryString(Integer.getInteger(a, 2) + Integer.getInteger(b, 2));
//    }
}
